#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;

}Node;

Node *RotateRight(Node *node)
{
    Node *t=node->left;
    node->left=t->right;
    t->right=node;
    return t;
}
Node *RotateLeft(Node *node)
{
    Node *t=node->right;
    node->right=t->left;
    t->left=node;
    return t;
}
Node *RotateLeftRight(Node *node)
{
    node->left=RotateLeft(node->left); 
    return RotateRight(node);
}
Node *RotateRightLeft(Node *node)
{
    node->right=RotateRight(node->right); 
    return RotateLeft(node);
}
int GetTreeHeight(Node *node)
{
    if(node==NULL)
    {
        return 0;
    }
    int leftheight=GetTreeHeight(node->left);
    int rightheight=GetTreeHeight(node->right);
    return (leftheight>rightheight?leftheight:rightheight)+1;

}
Node *InsertData(Node *node,int data)
{
    Node *newnode=(Node*)malloc(sizeof(Node));
    if(newnode==NULL)
    {
        printf("malloc error\n");
        return NULL;
    }
    newnode->data=data;
    newnode->left=NULL;
    newnode->right=NULL;
    if(node==NULL)
    {
        node=newnode;
    }
    else if(data<node->data)
    {
        node->left=InsertData(node->left,data);
        if(GetTreeHeight(node->left)-GetTreeHeight(node->right)>1)

        {
            if(data<node->left->data)
            {
                node=RotateRight(node);
            }
            else
            {
                node=RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right=InsertData(node->right,data);
        if(GetTreeHeight(node->left)-GetTreeHeight(node->right)<-1)

        {
            if(data<node->right->data)
            {
                node=RotateRightLeft(node);
            }
            else
            {
                node=RotateLeft(node);
            }
        }
    }
    return node;
}

void MidTravel(Node *node)
{
    if(node!=NULL)
    {
        MidTravel(node->left);
        printf("%d ",node->data);
        MidTravel(node->right);
    }
}

void PrevTravel(Node *node)
{
    if(node!=NULL)
    {
        printf("%d ",node->data);
        PrevTravel(node->left);
        PrevTravel(node->right);
    }
}
void main()
{
    Node *root=NULL;
    int a[]={1,2,3,4,5,6,7,8,9,10};
    for(int i=0;i<10;i++)
    {
        root=InsertData(root,a[i]);
    }
    PrevTravel(root);
    printf("\n");
    MidTravel(root);
    printf("\n");
    printf("%d\n",root->data);
}